package com.leetcode.联赛.力扣杯春季编程大赛;

import java.util.Arrays;

/**
 * @author: xiaomi
 * @date: 2021/4/5
 * @description: 1. 采购方案
 */
public class A_1_采购方案 {
    static A_1_采购方案 action = new A_1_采购方案();

    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
        test4();
    }

    static void test1() {
        //4
        int[] nums = new int[]{2, 2, 1, 9};
        int res = action.purchasePlansNotSoFaster(nums, 10);
        System.out.println("res = " + res);
    }

    static void test2() {
        //1
        int[] nums = new int[]{2, 5, 3, 5};
        int res = action.purchasePlansNotSoFaster(nums, 6);
        System.out.println("res = " + res);
    }

    static void test3() {
        //6
        int[] nums = new int[]{2, 2, 1, 3};
        int res = action.purchasePlansNotSoFaster(nums, 10);
        System.out.println("res = " + res);
        //System.out.println("res = " + res);
    }

    static void test4() {
        //6
        int[] nums = new int[]{5, 3, 1, 2};
        int res = action.purchasePlansNotSoFaster(nums, 7);
        System.out.println("res = " + res);
        //System.out.println("res = " + res);
    }

    /**
     * 没想到这就超时了
     *
     * @param nums
     * @param target
     * @return
     */
    public int purchasePlans(int[] nums, int target) {
        int len = nums.length;
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = target - nums[i];
        }
        //
        long res = 0;
        for (int i = 0; i < len; i++) {
            if (arr[i] < 0) {
                continue;
            }
            for (int j = i + 1; j < len; j++) {
                if (arr[i] >= nums[j]) {
                    res++;
                }
            }
        }
        return (int) (res % 1000000007);
    }

    /**
     * 只能通过二分法进行优化了
     * （有错误但是不知道哪里疏忽了,只能放弃二分了）
     *
     * @param nums
     * @param target
     * @return
     */
    public int purchasePlansFaster(int[] nums, int target) {
        int len = nums.length;
        int[] arr = new int[len];
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            arr[i] = target - nums[i];
        }
        long res = 0;
        for (int i = 0; i < len; i++) {
            if (arr[i] < 0) {
                continue;
            }
            int begin = i + 1, end = len;
            int mid = (end + begin) >> 1;
            boolean find = false;
            while (begin < end) {
                if (nums[mid] == arr[i]) {
                    find = true;
                    res += mid - i;
                    break;
                }
                if (nums[mid] < arr[i]) {
                    begin = mid + 1;
                } else {
                    end = mid;
                }
                mid = (end + begin) >> 1;
            }
            if (!find) {
                //没有找到
                if (begin == i + 1) {
                    if (begin < len && nums[begin] < arr[i]) {
                        res++;
                    }
                } else {
                    if (begin == len) {
                        if (nums[begin - 1] < arr[i]) {
                            res += begin - i - 1;
                        } else {
                            res += begin - i - 2;
                        }
                    } else {
                        if (nums[begin] < arr[i]) {
                            res += begin - i;
                        } else {
                            res += begin - i - 1;
                        }

                    }
                }


            }
        }
        return (int) (res % 1000000007);
    }

    /**
     * 哎，败给了找不到发生BUG 的测试用例！看了下次写代码的时候需要优先考虑可能的漏洞了！
     *
     * @param nums
     * @param target
     * @return
     */
    public int purchasePlansNotSoFaster(int[] nums, int target) {
        int len = nums.length;
        int[] arr = new int[len];
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            arr[i] = target - nums[i];
        }
        long res = 0;
        int endIndex = len - 1;
        for (int i = 0; i < len; i++) {
            if (arr[i] < 0) {
                continue;
            }
            if (endIndex <= i) {
                break;
            }
            boolean find = false;
            for (int j = endIndex; j > i; j--) {
                if (arr[i] >= nums[j]) {
                    find = true;
                    endIndex = j;
                    break;
                }
            }
            if (!find) {
                continue;
            }
            res += endIndex - i;
        }
        return (int) (res % 1000000007);
    }
}
